//创建一个优先队列，第一个参数是比较函数，第二个是数据
function PriorityQueue(comp, data) {
    this.comp = comp || function (a, b) { return a - b };
    this.data = data || [];
}

//队列初始化，也就是根据传进来的比较函数创建初始堆
PriorityQueue.prototype.init = function () {
    let len = this.data.length;
    //调用建堆函数
    heapSet(this.data, len, this.comp);
}

//入队，将入队元素放入数组最后，然后调用_up自底向上进行调整
PriorityQueue.prototype.push = function (item) {
    this.data.push(item);
    _up(this.data, this.comp);
}
//出队，将数组第一个元素出队
PriorityQueue.prototype.pop = function () {
    if (this.data.length === 0) return undefined;
    let item = this.data.shift();

    let len = this.data.length;
    //这里要注意，可能这个元素出去后，数组中没有其它元素，所以此时要判断一下
    if (len > 0) {
        //将最后一个元素移到第一个元素上，再自顶向下进行调整
        let temp = this.data.pop();
        this.data.unshift(temp);
        _down(this.data, 0, len, this.comp);
    }
    return item;
}
//建堆（自底向上建堆，调整是自顶向下调整）
function heapSet(data, len, comp) {
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        _down(data, i, len, comp);
    }
}

//自顶向下调整
function _down(data, index, len, comp) {
    while (2 * index + 1 < len) {
        let cur = 2 * index + 1;
        if (cur + 1 < len) cur = comp(data[cur + 1], data[cur]) >= 0 ? cur + 1 : cur;
        if (comp(data[index], data[cur]) < 0) {
            [data[index], data[cur]] = [data[cur], data[index]];
            index = cur;
        } else break;

    }
}
//自底向上调整
function _up(data, comp) {
    let index = data.length - 1;
    while (index !== 0) {
        let parentIndex = Math.floor((index - 1) / 2);
        if (comp(data[parentIndex], data[index]) < 0) {
            [data[parentIndex], data[index]] = [data[index], data[parentIndex]];
            index = parentIndex;
        } else break;
    }
}

